USACO 2025年1月铜牌

[USACO25JAN] Astral Superposition B

题目描述

注意：本题的时间限制为 4 秒，通常限制的 2 倍。

Bessie 正在使用她超酷的望远镜拍摄夜空中所有星星的照片。她的望远镜能够拍摄到一张 $N \times N$ （ $1 \leq N \leq 1000$ ）的星星照片，其中每个像素是一颗星星或者空旷的天空。每颗星星可由恰好一个像素表示，并且没有两颗不同的星星位于同一像素内。

一夜之间，一些奇怪的事情发生在了天空中的星星之上。每颗星星要么消失，要么向右移动 $A$ 像素，并且向下移动 $B$ 像素（ $0 \leq A, B \leq N$ ）。如果一颗星星消失或移动超出照片边界，它将不再出现在第二张照片中。

Bessie 在星星移动位置之前和之后拍了照片，但在 Mootoshop 中进行了一些实验后，她不小心将一张照片叠加到了另一张上。现在，她可以在两张照片都是天空的位置看到白色（white）像素，在星星仅存在于恰好一张照片的位置看到灰色（gray）像素，而在两张照片中都有星星的位置看到黑色（black）像素。Bessie 同时记得没有新的星星移动入第二张照片的范围，从而她的第一张照片包含了夜空中所有的星星。

对于 $T$ （ $1 \leq T \leq 1000$ ）个独立的测试用例，给定最终的照片，求在移动事件发生之前天空中星星的最小可能数量。如果不存在星星的排列可以产生给定的最终照片，输出 $- 1$ 。

输入格式

输入的第一行包含 $T$ ，以下为 $T$ 个测试用例。

每个测试用例的第一行包含 $N$ ， $A$ ， $B$ 。

以下 $N$ 行，每行表示叠加后的照片的一行。从上到下第 $i$ 行由一个字符串 $c_{i, 1} c_{i, 2} \dots c_{i, N}$ 表示，其中 $c_{i, j} \in {W,G,B}$ ，分别表示颜色为白色，灰色以及黑色。

输入保证所有测试用例的 $N^{2}$ 之和不超过 $10^{7}$ 。

输出格式

对于每一个测试用例，输出移动之前存在的星星的最小数量，或 $- 1$ 表示不可能。

输入输出样例 #1

输入 #1

1
3 0 0
WWB
BBB
GGG

输出 #1

输入输出样例 #2

输入 #2

3
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWW

输出 #2

4
-1
4

说明/提示

样例解释

在样例 #1 中，没有移动发生。第一张照片如下（. 表示天空，* 表示星星）：

..*
***
***

第二张照片中最下方一行的星星都消失了，如下：

..*
***
...

这是产生叠加后照片的唯一方式，所以初始时星星的最小可能数量为 $7$ 。

对于样例 #2，在第一个测试用例中，初始时至少有 $4$ 颗星星。如果我们令 $(r, c)$ 表示从上到下第 $r$ 行和从左到右第 $c$ 列的交点，一种可能性是它们最初位于 $(1, 1)$ ， $(3, 2)$ ， $(2, 2)$ 和 $(1, 3)$ 。除了位于 $(2, 2)$ 的星星消失之外，其他所有星星都移动了。

在第二个测试用例中，在给定的移动方式下，没有任何初始照片中的星星排列可以产生中间的黑色像素。

在第三个测试用例中，初始时至少有 $4$ 颗星星。一种可能性是它们最初位于 $(1, 1)$ ， $(1, 2)$ ， $(1, 3)$ 和 $(2, 1)$ 。在第二张照片中，原先位于 $(1, 1)$ 的星星消失了，原先位于 $(1, 3)$ 的星星移出了照片边界。其他两颗星星向右移动了 $1$ 像素。

子任务

测试点 3： $A = B = 0$ 。
测试点 4-7： $A = 1$ ， $B = 0$ ， $N \leq 10$ 。
测试点 8-9： $A = 1$ ， $B = 0$ 。
测试点 10-12：没有额外限制。

代码示例

c++

#include"iostream"
#include"algorithm"
using namespace std;
int T,n,a,b;
int pt[1005][1005];//代表最终图片的状态,'W'为0,'G'为1,'B'为2 
bool bor[1005][1005];//代表(i,j)位置的状态，如果为1就代表从(i-b,j-a)位置移动到(i,j)位置 
char c;
int main(){
	cin >> T;
	while(T--){
		memset(bor,0,sizeof(bor));//每组测试前，重置bor数组所有值为0
		int ans = 0;
		bool is_c = 1;
		cin >> n >> a >> b;
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++){
				cin >> c;
				if(c == 'W'){
					pt[i][j] = 0;
				}else if (c == 'G'){
					pt[i][j] = 1;
				}else if(c == 'B'){
					pt[i][j] = 2;
				}
				
				if(pt[i][j] == 2){//判断两张图片的(i,j)是否都能得到* 
					if(j-a >= 1 && i-b >= 1 && pt[i-b][j-a] > 0)//边界判断和判断是否满足移动条件 
						pt[i-b][j-a]--,pt[i][j]--,ans++,bor[i][j] = 1;
					else is_c = 0;
				}
			}
		if(!is_c){ 
			cout << "-1\n"; continue;
		}
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				if(pt[i][j] == 1){//判断当前灰点，能否通过第一张图片移动得到 
					if(!(!bor[i][j] && j-a >= 1 && i-b >= 1 && pt[i-b][j-a] > 0 && (a||b)))
						ans++;//不能通过平移得到就只能在第一张图片的(i,j)位置放置一颗* 
					else pt[i][j]--;
				}
		cout << ans << "\n";
	}
	return 0;
}

[USACO25JAN] It's Mooin' Time II B

题目描述

Farmer John 正在试图向 Elsie 描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。他说「竞赛中我最喜欢的部分是 Bessie 说『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

Elsie 仍然不理解，所以 Farmer John 将竞赛以文本文件形式下载，并试图解释他的意思。竞赛被定义为一个包含 $N$ （ $1 \leq N \leq 10^{6}$ ）个整数的数组 $a_{1}, a_{2}, \dots, a_{N}$ （ $1 \leq a_{i} \leq N$ ）。Farmer John 定义哞叫为一个包含三个整数的数组，其中第二个整数等于第三个整数，但不等于第一个整数。一种哞叫被称为在竞赛中发生，如果可以从数组中移除整数，直到只剩下这一哞叫。

由于 Bessie 据称「在整个竞赛中一直哞哞叫」，请帮助 Elsie 计算竞赛中发生的不同哞叫的数量！两种哞叫是不同的，如果它们并非由相同的整数以相同的顺序组成。

输入格式

输入的第一行包含 $N$ 。

第二行包含 $N$ 个空格分隔的整数 $a_{1}, a_{2}, \dots, a_{N}$ 。

输出格式

输出竞赛中发生的不同哞叫的数量。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 "long"，C/C++ 中的 "long long"）。

输入输出样例 #1

输入 #1

6
1 2 3 4 4 4

输出 #1

说明/提示

样例解释

竞赛包含三种不同的哞叫："1 4 4"，"2 4 4" 和 "3 4 4"。

子任务

测试点 2-4： $N \leq 10^{2}$ 。
测试点 5-7： $N \leq 10^{4}$ 。
测试点 8-11：没有额外限制。

代码示例

c++

#include"iostream"
#include"algorithm"
using namespace std;
const int N = 1e6 + 10;
int a[N],b[N],c[N],s[N];
//a用来存储输入序列值
//b用来作为计数统计，例如：b[10]=2，就代表数值10出现了两次。
//c[i]用来存储每个输入值第一次出现的位置，例如：c[10] = 1，就代表数值10是第一个用户输入的数据值。
//s用来统计不同值的个数和，例如：s[10]=4，就代表前面输入的10个数据，去重后只有4种。
long long res = 0;
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);
	for(int i = 1; i <= n; i ++)
		if(!c[a[i]]) c[a[i]] = i,s[i] = s[i - 1] + 1;
		else s[i] = s[i - 1];
	for(int i = n; i >= 1; i --)//需要从后向前
		if(++ b[a[i]] == 2) res += s[i - 1] - (c[a[i]] < i);//需要排除BBB的情况
	cout<<res<<endl;
	return 0;
}

[USACO25JAN] Cow Checkups B

题目描述

注意：我们建议使用 Python 以外的其他语言以获得本题目的全部分数。

Farmer John 的 $N$ （ $1 \leq N \leq 7500$ ）头奶牛站成一行，奶牛 $1$ 在队伍的最前面，奶牛 $N$ 在队伍的最后面。FJ 的奶牛也有许多不同的品种。他用从 $1$ 到 $N$ 的整数来表示每一品种。队伍从前到后第 $i$ 头奶牛的品种是 $a_{i}$ （ $1 \leq a_{i} \leq N$ ）。

FJ 正在带他的奶牛们去当地的奶牛医院进行体检。然而，奶牛兽医非常挑剔，仅愿意当队伍中第 $i$ 头奶牛为品种 $b_{i}$ （ $1 \leq b_{i} \leq N$ ）时对其进行体检。

FJ 很懒惰，不想完全重新排列他的奶牛。他将执行以下操作恰好一次。

选择两个整数 $l$ 和 $r$ ，使得 $1 \leq l \leq r \leq N$ 。反转队伍中第 $l$ 头奶牛到第 $r$ 头奶牛之间的奶牛的顺序。 FJ 想要衡量这种方法有多少效果。对于每一个 $c = 0 \dots N$ ，请帮助 FJ 求出使得恰好 $c$ 头奶牛被检查的不同操作 $(l, r)$ 的数量。两种操作 $(l_{1}, r_{1})$ 和 $(l_{2}, r_{2})$ 不同，当且仅当 $l_{1} \neq l_{2}$ 或者 $r_{1} \neq r_{2}$ 。

输入格式

输入的第一行包含 $N$ 。

第二行包含 $a_{1}, a_{2}, \dots, a_{N}$ 。

第三行包含 $b_{1}, b_{2}, \dots, b_{N}$ 。

输出格式

输出 $N + 1$ 行，第 $i$ 行包含使得 $i - 1$ 头奶牛被检查的不同操作 $(l, r)$ 的数量。

输入输出样例 #1

输入 #1

3
1 3 2
3 2 1

输出 #1

输入输出样例 #2

输入 #2

3
1 2 3
1 2 3

输出 #2

输入输出样例 #3

输入 #3

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

输出 #3

说明/提示

样例解释

/样例 #1：

如果 FJ 选择 $(l = 1, r = 1)$ ， $(l = 2, r = 2)$ 或 $(l = 3, r = 3)$ ，则没有奶牛将会被检查。注意这些操作并没有改变奶牛的位置。以下操作会导致一头奶牛被检查。

$(l = 1, r = 2)$ ：FJ 反转第一头和第二头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[3, 1, 2]$ 。第一头奶牛将会被检查。
$(l = 2, r = 3)$ ：FJ 反转第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[1, 2, 3]$ 。第二头奶牛将会被检查。
$(l = 1, r = 3)$ ：FJ 反转第一头，第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[2, 3, 1]$ 。第三头奶牛将会被检查。

样例 #2

三种导致 $3$ 头奶牛被检查的可能操作为 $(l = 1, r = 1)$ ， $(l = 2, r = 2)$ 和 $(l = 3, r = 3)$ 。

样例 #3

两种导致 $4$ 头奶牛被检查的可能操作为 $(l = 4, r = 5)$ 和 $(l = 5, r = 7)$ 。

子任务

测试点 4-6: $N \leq 100$
测试点 7-13: 无特殊限制

代码示例

c++

#include"iostream"
#include"algorithm"
using namespace std;
int n,a[7505],b[7505],ans[7505],cnt,l,r;
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=n;i++) cin>>b[i];
    for(int i = 1;i<=n;i++) if(a[i]==b[i]) cnt++;//记录好原本就对应好的状态个数 
    for(int i = 1;i<=n;i++){//枚举每一个节点作为中心节点，然后以这个节点向左右扩展区间判断。 
        int tmp=cnt;
        l=i,r=i;
        while(l>=1&&r<=n){
            if(a[l]==b[l]&&a[l]!=b[r]) tmp--;
            if(a[r]==b[r]&&a[r]!=b[l]) tmp--;
            if(a[l]!=b[l]&&a[l]==b[r]) tmp++;
            if(a[r]!=b[r]&&a[r]==b[l]) tmp++;
            ans[tmp]++;
            l--,r++;
        }
        if(i==n) continue;
        //枚举长度为偶数的区间
        l=i,r=i+1;
        tmp=cnt;
        while(l>=1&&r<=n){
            if(a[l]==b[l]&&a[l]!=b[r]) tmp--;
            if(a[r]==b[r]&&a[r]!=b[l]) tmp--;
            if(a[l]!=b[l]&&a[l]==b[r]) tmp++;
            if(a[r]!=b[r]&&a[r]==b[l]) tmp++;
            ans[tmp]++;
            l--,r++;
        }
    }
    for(int i = 0;i<=n;i++) cout<<ans[i]<<'\n';
}

优化后的具体步骤

初始计数：计算初始状态下被检查的奶牛数量 cnt，与优化前相同。
枚举中间点：
- 对于每个可能的中间点 i，向外扩展区间 [l, r]，分别处理长度为奇数和偶数的区间。
动态维护计数：
- 在扩展区间时，动态维护被检查奶牛的数量 tmp。
- 每次扩展区间时，判断对称位置上的奶牛是否满足被检查条件，并更新 tmp。
具体计算：
- 中间点 i = 1：
  - 奇数长度区间：[1, 1] → [0, 2]（无效），被检查奶牛数量为 0。
  - 偶数长度区间：[1, 2] → [0, 3]（无效），被检查奶牛数量为 1。
- 中间点 i = 2：
  - 奇数长度区间：[2, 2] → [1, 3]，被检查奶牛数量为 1。
  - 偶数长度区间：[2, 3] → [1, 4]（无效），被检查奶牛数量为 1。
- 中间点 i = 3：
  - 奇数长度区间：[3, 3] → [2, 4]（无效），被检查奶牛数量为 0。
结果统计：
- ans[0] = 3（区间 [1,1]、[2,2]、[3,3]）
- ans[1] = 3（区间 [1,2]、[2,3]、[1,3]）
- 其他 ans 值为 0。

区间覆盖分析

长度为奇数的区间：
- 以中间点 i 为起点，向两边扩展，生成的区间包括 [i, i]、[i-1, i+1]、[i-2, i+2] 等。
- 例如，当 i = 2 时，生成的区间包括 [2, 2]、[1, 3]、[0, 4]（无效）等。
长度为偶数的区间：
- 以中间点 i 和 i+1 为起点，向两边扩展，生成的区间包括 [i, i+1]、[i-1, i+2]、[i-2, i+3] 等。
- 例如，当 i = 1 时，生成的区间包括 [1, 2]、[0, 3]（无效）等。

通过这种方式，优化后的代码能够生成所有可能的区间 [l, r]，与优化前的枚举方式生成的区间集合完全相同。

具体举例

假设 n = 3，优化后的代码生成的区间如下：

中间点 i = 1：
- 奇数长度区间：[1, 1]、[0, 2]（无效）
- 偶数长度区间：[1, 2]、[0, 3]（无效）
中间点 i = 2：
- 奇数长度区间：[2, 2]、[1, 3]
- 偶数长度区间：[2, 3]、[1, 4]（无效）
中间点 i = 3：
- 奇数长度区间：[3, 3]、[2, 4]（无效）
- 偶数长度区间：无（因为 i = 3 是最后一个点，无法生成偶数长度区间）

生成的有效区间包括：

[1, 1]、[1, 2]、[2, 2]、[1, 3]、[2, 3]、[3, 3]

这些区间与优化前的枚举方式生成的区间完全相同。

结论
- 优化后的代码通过枚举中间点并向外扩展区间的方式，能够覆盖所有可能的区间 [l, r]，因此优化后的区间集合与优化前的区间集合是相同的。优化后的代码在时间复杂度上更优，能够高效地解决问题。
- 优化前：对于每个区间 [l, r]，都需要遍历区间内的所有元素来计算被检查的奶牛数量，时间复杂度为 O(N3)。
- 优化后：通过枚举中间点并利用对称性动态维护计数，避免了对每个区间进行逐一判断，时间复杂度降低为 O(N2)。

USACO 2025年1月铜牌 ​

[USACO25JAN] Astral Superposition B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

输入输出样例 #2 ​

输入 #2 ​

输出 #2 ​

说明/提示 ​

样例解释 ​

子任务 ​

代码示例 ​

[USACO25JAN] It's Mooin' Time II B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

样例解释 ​

子任务 ​

代码示例 ​

[USACO25JAN] Cow Checkups B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

输入输出样例 #2 ​

输入 #2 ​

输出 #2 ​

输入输出样例 #3 ​

输入 #3 ​

输出 #3 ​

说明/提示 ​

样例解释 ​

/样例 #1： ​

样例 #2 ​

样例 #3 ​

子任务 ​

代码示例 ​

优化后的具体步骤 ​

区间覆盖分析 ​

具体举例 ​

结论 ​

USACO 2025年1月铜牌

[USACO25JAN] Astral Superposition B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

样例解释

子任务

代码示例

[USACO25JAN] It's Mooin' Time II B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例解释

子任务

代码示例

[USACO25JAN] Cow Checkups B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

说明/提示

样例解释

/样例 #1：

样例 #2

样例 #3

子任务

代码示例

优化后的具体步骤

区间覆盖分析

具体举例

结论